package LBLD新算法;

import org.junit.Test;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
    每个节点只处理自己（单cur思想）
    做完题一定写入表格
*/
public class 寻找两个正序数组的中位数4 {
    @Test
    public void test() {
        int[] p1={1,2};
        int[] p2={3,4};
        System.out.println(findMedianSortedArrays(p1, p2));
    }


    public double findMedianSortedArrays(int[] a, int[] b) {
        int n1=a.length,n2=b.length;
        if(n1>n2){
            return findMedianSortedArrays(b,a);
        }
        //r不要n1-1,分界线可以=n1的
        int l=0,r=n1;
        while(l<=r){
            System.out.println(l+","+r);
            int m = l+r>>1;
            int j = (n1+n2+1)/2-m;
            if(m!=0&&j!=n2 && a[m-1]>b[j])
                r=m-1;
            else if(m!=n1&&j!=0 && a[m]<b[j-1])
                l=m+1;
            else {
                int maxL=0;
                if(m==0){
                    maxL = b[j-1];
                }
                else if(j==0){
                    maxL = a[m-1];
                }
                else maxL = Math.max(a[m-1],b[j-1]);
                //n1+n2奇数在这里，要不下面else拿不到上面的maxL
                if((n1+n2)%2==1) return maxL;
                //偶数
                else{
                    int minR=0;
                    //0的被奇数左侧算好，只剩m右边界特殊了
                    if(m==n1){
                        minR = b[j];
                    }
                    else if(j==n2){
                        minR = a[m];
                    }
                    else minR = Math.min(a[m],b[j]);
                    return (maxL+minR)/2.0;
                }
            }
        }
        return -1.0;
    }
}
